package _76

/*
时间复杂度：O()
空间复杂度：O()

TODO:如何求时间复杂度??

解：题目求从1->target的操作次数，可以转换为从target->1的操作次数
将target开成二进制数，最快的变成1的方式:
一、maxDoubles>0(maxDoubles为翻倍操作的最大限制次数)
	1.当target为偶数,则右移一位
	2.否则，将target-1
二、maxDoubles == 0
	则右移的操作已经用完了，所以剩下的都是-1的操作，可以直接退出,然后ans+target-1即是总操作次数
*/

func minMoves(target int, maxDoubles int) int {
	ans := 0
	for target != 1 {
		if maxDoubles == 0 {
			break
		}
		if target&1 == 0 {
			target /= 2
			maxDoubles--
		} else {
			target--
		}
		ans++
	}
	return ans + target - 1
}
